//从n(>2)开始计算，用F(n-1)和F(n-2)两个数相加求出结果，
//这样就避免了大量的重复计算，它的效率比递归算法快得多，
//算法的时间复杂度与n成正比，即算法的时间复杂度为O(n).
#include <iostream>

using namespace std;

int64_t Fib(int n)
{
    if(n == 0)
        return 0;
    if(n <= 2)
        return 1;
    //first 是第n-2个数；second是第n-1个数
    int64_t first = 0;
    int64_t second = 1;
    while(0 < n--)
    {
        second += first; 
        first = second - first; 
    }
    return first + second;
}

int main(int argc, char const *argv[])
{
    for(int i =0; i< 50;i++)
    {
        cout << "Fib(" << i << ")=" << Fib(i) <<endl;
    }
    return 0;
}
